package 优先算法.二分查找.在排序数组中查找元素的第一个和最后一个位置;
/**
 * https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/submissions/549453383/
 */

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Solution so = new Solution();
        int[] arr = {5,7,7,8,8,10};
        int[] rel = so.searchRange(arr, 8);
        System.out.println(Arrays.toString(rel));
    }
}
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = 0,right = nums.length-1;
        int[] rel = {-1,-1};
        int LIndex = -1, RIndex = -1;
        if(nums.length == 0) return rel;
        //查找左端点
        while(left < right){
            int mid = left + (right -left)/2;// 1 2 3 4这样会选中 “2”
            if(nums[mid] < target){
                left = mid + 1;
            }
            if(nums[mid] >= target){
                right = mid;
            }
        }
        if(nums[right] == target){
            LIndex = right;
        }

        //更新左右指针
        left = 0;
        right = nums.length-1;

        //查找右端点
        while(left < right){
            int mid = left +(right - left + 1)/2;// 1 2 3 4这样会选中 “3”
            if(nums[mid] <= target){
                left = mid;
            }
            if(nums[mid] > target){
                right = mid -1;
            }
        }
        if(nums[right] == target){
            RIndex = right;
        }
        rel[0]=LIndex;
        rel[1]=RIndex;
        return rel;
    }
}